(COCI 2017/2018 6) Alkemija

题解

题意

共有 N 种不同的物质，编号为 1 到 N。

初始时，Joško 拥有 M 种物质 A₁, A₂, …, A_M，每种物质的量无限。

已知 K 个炼金反应，每个反应的形式为：

• 如果拥有物质集合 {X₁, X₂, …, X_L} 中的所有物质，则可以消耗它们（但实际中物质无限，所以相当于一旦条件满足，就可以永久获得产物），得到物质集合 {Y₁, Y₂, …, Y_R}。

反应可以反复使用，且获得的物质可以继续用于触发其他反应。

求最终能够获得的所有物质的集合，并按升序输出物质数量及具体编号。

数据范围

• 1 ≤ M ≤ N ≤ 100,000
• 1 ≤ K ≤ 100,000
• 对于每个反应：1 ≤ L, R ≤ N
• 所有反应的 L 之和 ≤ 100,000
• 所有反应的 R 之和 ≤ 100,000
• 对于 60% 的数据：N, K ≤ 500，且所有 L 之和与所有 R 之和 ≤ 500

解法

这道题需要用到神秘的人类智慧。

首先，由于我们不需要考虑物质的数量，对于每一个反应，我们可以把他当作若我们用后集合$X$中的每一个元素，就可以拥有集合$Y$中的每一个元素。

有一种很显然的暴力做法，就是考虑每次暴力枚举每一个反应，如果我们当前拥有的物质满足反应需求，就将所有产物加入我们拥有的物质集合。这种做法的时间复杂度是$O(N \cdot (\sum L+ \sum R))$期望得分$60$。

接下来就有两种思考方向，我考场上都想到了但都没想到底W_W

$1.$我们发现这个暴力很慢的原因是额外枚举了很多次无用的反应，对于这道题而言，如果要时间复杂度正确，那么我们就需要让所有反应只被枚举常数次。

那么我们什么时候枚举这个反应呢？一个很显然的答案就是当我们拥有所有这个反应的原材料时。

那么我们接下来的问题就呼之欲出了，我们要怎么知道这个反应的原材料我们全部拥有了？而我们枚举了这个反应后，要怎么清楚得到的产物时那些反应的原材料？

其实这个问题很好解决，我们把这两个信息存其来就行了！

对于每一个反应，我们存一个数组$du_i$ $($至于为什么取这个变量名后面在说$)$ 表示这个反应缺少的原材料的数量，另一个$vector$数组某个材料分别作为那些反应的原材料。

我们使用一个队列，将初始材料入队，每次将当前材料能够参与的反应$du_i-1$当一个反应的$du_i$为$0$时就可以将所有以前没有的产物加入队列中，一直进行队列为空结束。

由于每种物质只会进，出队一次，每个反应的原材料和产物分别最多指挥枚举一次。

总时间复杂度为$O(N+\sum L + \sum R)$

$2.$ 第二个思考方向是建图。因为我们发现这种类似$A$是$B$的前提的问题，我们通常可以通过在关系中连边，转换为图论的问题或者更方便我们思考。

那么这道题也是同理，一个直觉很容易想到的想法就是在一个反应中让每个原材料对于每一个产物连边，但是我们意识到，一个产物不一定只由一个反应产生，而我们只需满足其中一个反应就能得到这个产物，而且这么算边数也不对但数据太水有人靠这个过了，但那个人自己造的hack给自己hack掉了。

那么我们运用人类智慧想到一个新的建图方式，我们给每个反应建一个特殊节点，然后我们将所有原材料向这个反应对应的点连边，然后在由这个点指向所有原材料。

但即使如此我们依然没法直接跑拓扑，但实际上已经可做了。

我们可以采用类似拓扑的方式，对于反应对应的节点我们要让他入度为$0$才能入队，然后反应对应的节点出队时可以直接将所有产物的节点入队。

然后我们发现$1,2$方法殊途同归实际上是同一种做法！那你在那噼里啪啦将什么

代码

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,k;
vector<int> e[N];
vector<int> E[N];
int du[N];
bool vis[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    queue<int> q;
    for(int i=1;i<=m;i++) 
    {
        int x;
        cin>>x;
        q.push(x);
        vis[x]=true;
    }
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        int l,r;
        cin>>l>>r;
        for(int j=1;j<=l;j++) 
        {
            int x;
            cin>>x;
            e[x].push_back(i);
        }
        du[i]=l;
        for(int j=1;j<=r;j++) 
        {
            int x;
            cin>>x;
            E[i].push_back(x);
        }
    }   
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=0;i<e[x].size();i++)
        {
            int y=e[x][i];
            du[y]--;
            if(!du[y])
            {
                for(int j=0;j<E[y].size();j++)
                {
                    int z=E[y][j];
                    if(vis[z]) continue;
                    vis[z]=true;
                    q.push(z);
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++) if(vis[i]) ans++;
    cout<<ans<<'\n';
    for(int i=1;i<=n;i++) if(vis[i]) cout<<i<<' ';
    return 0;
}